#include <bits/stdc++.h>
using namespace std;

/*
2300. 咒语和药水的成功对数
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。

同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success ，那么它们视为一对 成功 的组合。

请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。

 

示例 1：

输入：spells = [5,1,3], potions = [1,2,3,4,5], success = 7
输出：[4,0,3]
解释：
- 第 0 个咒语：5 * [1,2,3,4,5] = [5,10,15,20,25] 。总共 4 个成功组合。
- 第 1 个咒语：1 * [1,2,3,4,5] = [1,2,3,4,5] 。总共 0 个成功组合。
- 第 2 个咒语：3 * [1,2,3,4,5] = [3,6,9,12,15] 。总共 3 个成功组合。
所以返回 [4,0,3] 。
示例 2：

输入：spells = [3,1,2], potions = [8,5,8], success = 16
输出：[2,0,2]
解释：
- 第 0 个咒语：3 * [8,5,8] = [24,15,24] 。总共 2 个成功组合。
- 第 1 个咒语：1 * [8,5,8] = [8,5,8] 。总共 0 个成功组合。
- 第 2 个咒语：2 * [8,5,8] = [16,10,16] 。总共 2 个成功组合。
所以返回 [2,0,2] 。
 

提示：

n == spells.length
m == potions.length
1 <= n, m <= 105
1 <= spells[i], potions[i] <= 105
1 <= success <= 1010
*/

// 法一
class Solution {
public:
    using ll = long long;
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        int n = spells.size(), m = potions.size();
        vector<int> ans(n, 0); // 每个咒语的成功对数

        // 后续二分
        sort(potions.begin(), potions.end());
        for (int i = 0; i < n; i++) {
            ll s = spells[i];   // 怕溢出
            // min pow 向上取整
            ll p_min = (success + s - 1) / s;
            // 第一个大于最小药水能量的位置
            auto it = lower_bound(potions.begin(), potions.end(), p_min);

            // 达标 = total - first index
            ans[i] = m - (it - potions.begin());
        }
        return ans;
    }
};

// 法二
class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        int mx = ranges::max(potions);// 找到药水能量的最大值，用于确定计数数组的大小        
        vector<int> cnt(mx + 1);// 计数数组：cnt[y]表示能量为y的药水数量
        
        // 统计每个能量值的药水数量
        for (int y : potions) cnt[y]++;
        
        // 计算后缀和：cnt[i]变为能量 >= i 的药水总数（从大到小累加）
        for (int i = mx - 1; i >= 0; i--) {
            cnt[i] += cnt[i + 1];
        }
        // 遍历每个咒语，计算成功对数
        for (int& x : spells) {
            // 计算当前咒语需要的最小药水能量：low = ceil(success / x)
            // 公式 (success-1)/x + 1 等价于向上取整，避免浮点数运算
            long long low = (success - 1) / x + 1;
            // 若最小能量不超过最大药水能量，则取对应后缀和；否则为0
            x = (low <= mx) ? cnt[low] : 0;
        }
        return spells; // 复用咒语数组存储结果
    }
};